
//散列算法的作用是尽可能快地在数据结构中找到一个值
//如果要在数据结构中获得一个值（使用get方法），需要迭代整个数据结构来找到它。
//如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址

import { ValuePair } from "./Dictionary";
import { List, ListNode } from "./List";
import { defaultToString } from "./utils";

export class HashMap<K, V>{

    private _table: { [key: number]: ValuePair<K, V> };

    public constructor() {
        this._table = {};
    }

    public put(key: K, vaule: V) {
        if (key != null && vaule != null) {
            const hashCode = this.hashCode(key);
            this._table[hashCode] = new ValuePair<K, V>(key, vaule);
            return true;
        }
        return false;
    }

    public remove(key: K) {
        const hash = this.hashCode(key);
        const valuePair = this._table[hash];
        if (valuePair != null) {
            delete this._table[hash];
            return true;
        }
        return false;
    }

    public get(key: K) {
        const valuePair = this._table[this.hashCode(key)];
        return valuePair == null ? undefined : valuePair.value;
    }

    public hashCode(key: K) {
        return this.djb2HashCode(key);
    }

    public clear() {
        this._table = {};
    }

    public toString() {
        if (this.length == 0) {
            return '';
        }
        const keys = Object.keys(this._table);
        let objString = `{${keys[0]} => ${this._table[Number(keys[0])].toString()}}`;
        for (let i = 1; i < keys.length; i++) {
            objString = `${objString},{${keys[i]} => ${this._table[Number(keys[i])].toString()}}`;
        }
        return objString;
    }

    public get table() {
        return this._table;
    }

    public get length() {
        return Object.keys(this._table).length;
    }

    private loseloseHashCode(key: K) {
        if (typeof key == "number") {
            return key;
        }
        const tableKey = defaultToString(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;//为了规避操作数超过数值变量最大表示范围的风险。
    }
    //社区用的比较好用的散列(哈希)函数
    private djb2HashCode(key: K) {
        const tableKey = defaultToString(key);
        let hash = 5381;//初始化一个hash变量并赋值为一个质数（大多数实现都使用5381）
        for (let i = 0; i < tableKey.length; i++) {
            hash = (hash * 33) + tableKey.charCodeAt(i); //迭代参数key，将hash与33相乘（用作一个幻数(编程中指直接使用的常数） 当前迭代到的字符的ASCII码值相加
        }
        return hash % 1013; //使用相加的和与另一个随机质数相除的余数，比我们认为的散列表大小要大
    }
}

//散列表中的冲突
// loseloseHashCode方法获得的hascode 存在重复问题，这会使数据丢失
// 处理方式1 
// 分离链接  (每个位置创建个链表将元素存储在里面)
// 线性探查  (当想向表中某个位置添加一个新元素的时候，如果索引为position的位置已经被占据了，就尝试position+1的位置。如果position+1的位置也被占据了，就尝试position+2的位置，以此类推，直到在散列表中找到一个空闲的位置。)

export class HashMapSeparateChainin<K, V>
{
    private _table: { [key: number]: List<ValuePair<K, V>> };

    public constructor() {
        this._table = {};
    }

    public put(key: K, value: V) {
        if (key != null && value != null) {
            const position = this.hashCode(key);
            if (this._table[position] == null) {
                this._table[position] = new List<ValuePair<K, V>>();
            }
            this._table[position].push(new ValuePair(key, value));
            return true;
        }
        return false;
    }

    public get(key: K) {
        const position = this.hashCode(key);
        const list = this._table[position];
        if (list != null && list.length != 0) {
            let current: ListNode<ValuePair<K, V>> | null = list.begin();
            while (current != null) {
                if (current.data?.key === key) {
                    return current.data.value;
                }
                current = current.next;
            }
        }
        return undefined;
    }

    public remove(key: K) {
        const position = this.hashCode(key);
        const list = this._table[position];
        if (list != null && list.length != 0) {
            let current: ListNode<ValuePair<K, V>> | null = list.begin();
            while (current != null) {
                if (current.data?.key === key) {
                    list.remove(current);
                    if (list.length == 0) {
                        delete this._table[position];
                    }
                    return true;
                }
                current = current.next;
            }
        }
        return false;
    }

    public hashCode(key: K) {
        return this.loseloseHashCode(key);
    }

    private loseloseHashCode(key: K) {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = defaultToString(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }

}
